CSE 311: Section 5

Task 1 – Regular Expressions

For each of the following, construct regular expressions that match the given set of strings:

1. Base 10 numbers (e.g., there should be no leading zeroes).

2. All base-3 numbers that are divisible by 3.

3. All binary strings that contain the substring “111”, but not the substring “000”.

Task 2 – CFGs

For each of the following, construct a context-free grammar that generates the given set of strings.

If your grammar has more than one variable (also called a non-terminal symbol), write a sentence describing what sets of strings you expect each variable in your grammar to generate. For example, if your grammar was: $$\begin{array}{rcl}\mathbf{S}& \to & \mathbf{E}\mid \mathbf{O}\\ \mathbf{O}& \to & \mathbf{E}\mathbf{C}\\ \mathbf{E}& \to & \mathbf{E}\mathbf{E}\mid \mathbf{C}\mathbf{C}\\ \mathbf{C}& \to & 0\mid 1\end{array}$$

You could say “$C$ generates binary strings of length one, $E$ generates (non-empty) even length binary strings, and $O$ generates odd length binary strings.” It is also fine to use a regular expression, rather than English, to describe the strings generated by a variable (assuming such a regular expression exists). If you only use one variable (i.e., $S$), an explanation is not required but you should provide the grammar.

1. All binary strings that start with 11.

2. All binary strings that contain at most one 1.

3. All binary strings that contain at least three 1’s.

4. All strings over {0,1,2} with the same number of 1s and 0s and exactly one 2.

   Hint: Try modifying the grammar from lecture for binary strings with the same number of 1s and 0s. (You may need to introduce new variables in the process.)

Task 3 – FSM Design

Let $\Sigma = \{0, 1, 2, 3\}$. Construct FSMs to recognize each of the following languages.

For all states in your FSM, include “documentation” for them by describing, in English, the set of strings that end in that state.

1. All binary strings that end with two 1’s.

2. All strings whose digits sum to an even number.




Let $\Sigma = \{0, 1\}$. Construct FSMs to recognize each of the following languages.

For all states in your FSM, include “documentation” for them by describing, in English, the set of strings that end in that state.

3. All strings that do not contain the substring $101$.

4. All strings containing at least two $0$’s and at most one $1$.

Task 4 – Good, Good, Good, Good Relations

For each of the relations below, determine whether or not it has each of the properties of reflexivity, symmetry, antisymmetry, and/or transitivity. If a relation has a property, simply say so without any further explanation. If a relation does not have a property, state a counterexample, but do not explain your counterexample further.

1. Let $R = \{(x, y)\;:\;x = y + 1\}$ on $\mathbb{N}$.

2. Let $R = \{(x, y) \;:\;x^2 = y^2\}$ on $\mathbb{R}$.
   

3. Let $R = \{(x, y)\;:\; \textsf{len}(xy) \text{ is even}\}$ on $\{0,1\}^*$.